package regAlloc;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Hashtable;

import temp.Temp;
import temp.TempMap;

public class Color implements TempMap {
	Hashtable<temp.Temp, temp.Temp> map = new Hashtable<temp.Temp, temp.Temp>();
	Hashtable<temp.Temp, Integer> spillMap = new Hashtable<temp.Temp, Integer>();

	private int getSpillPos(mips.Frame frame, temp.Temp tmp) {
		if (spillMap.get(tmp) != null)
			return spillMap.get(tmp).intValue();
		else {
			int pos = -frame.allocSpillVar();
			spillMap.put(tmp, new Integer(pos));
			return pos;
		}
	}
	
	temp.Temp getColoredTemp(temp.Temp n) {
		return map.get(n);
	}
	
	public assem.InstrList rebuildProg(mips.Frame frame, assem.InstrList il) {
		assem.InstrList last = null;
		ArrayList<temp.Temp> tReg = new ArrayList<temp.Temp>();
		map.put(frame.RA(), frame.RA());
		map.put(frame.V1(), frame.V1());
		tReg.add(frame.RA());
		tReg.add(frame.V1());
		
		for (assem.InstrList tmp = il; tmp != null; tmp = tmp.tail) {
			int cnt = 0;
			assem.InstrList next = tmp.tail;
			for (temp.TempList j = tmp.head.use(); j != null; j = j.tail)
			if (getColoredTemp(j.head) == null){
				if (last == null)
					il = last = new assem.InstrList(
							new assem.OPER("\tlw\t'd0, " + (getSpillPos(frame, j.head)) + "('s0)\n", new temp.TempList(tReg.get(cnt), null), new temp.TempList(frame.FP(), null)),
							tmp);
				else {
					last = last.tail = new assem.InstrList(
							new assem.OPER("\tlw\t'd0, " + (getSpillPos(frame, j.head)) + "('s0)\n", new temp.TempList(tReg.get(cnt), null), new temp.TempList(frame.FP(), null)),
							tmp);
				}
				j.head = tReg.get(cnt); 
				cnt ++;
			}
			cnt = 0;
			for (temp.TempList j = tmp.head.def(); j != null; j = j.tail)
			if (getColoredTemp(j.head) == null) {
				if (next == null)
					next = tmp.tail = new assem.InstrList(
							new assem.OPER("\tsw\t's0, " + (getSpillPos(frame, j.head)) + "('s1)\n", null, new temp.TempList(tReg.get(cnt), new temp.TempList(frame.FP(), null))),
							null
							);
				else
					next = tmp.tail = new assem.InstrList(
							new assem.OPER("\tsw\t's0, " + (getSpillPos(frame, j.head)) + "('s1)\n", null, new temp.TempList(tReg.get(cnt), new temp.TempList(frame.FP(), null))),
							next
							);
				j.head = tReg.get(cnt);
				cnt ++;
			}
			last = tmp;
		}
		return il;
	}

	public temp.TempList spills() {
		return null;
	}

	public String tempMap(Temp t) {
		// TODO Auto-generated method stub
//		if (map.get(t) == null) {
//			System.out.println();
//		}
		return map.get(t).toString();
	}

	public Color(InterferenceGraph ig, temp.TempList registers) {
		graph.NodeList nl = ig.nodes();
		java.util.Stack<graph.Node> ns = new java.util.Stack<graph.Node>();
		int maxDeg, cnt = 0;
		graph.Node maxNode, spillNode;

		for (temp.TempList i = registers; i != null; i = i.tail)
			cnt ++;
		for (graph.NodeList i = ig.nodes(); i != null; i = i.tail) 
			if (ig.gtemp(i.head).getType() != 0)
				map.put(ig.gtemp(i.head), ig.gtemp(i.head));

		HashSet<graph.Node> added = new HashSet<graph.Node>();

		do {
			maxDeg = -1;
			maxNode = null;
			for (graph.NodeList i = nl; i != null; i = i.tail)
				if (!added.contains(i.head) && ig.gtemp(i.head).getType() == 0) {
					int iCnt = i.head.outDegree();
					if (iCnt < cnt && iCnt > maxDeg){
						maxDeg = iCnt;
						maxNode = i.head;
					}
				}
			spillNode = null;
			if (maxNode != null) {
				ns.push(maxNode);
				added.add(maxNode);
				for (graph.NodeList i = maxNode.pred(); i != null; i = i.tail)
				if (!added.contains(i.head))
					ig.rmEdge(i.head, maxNode);
				spillNode = maxNode;
			}
			else {
				int minSpillCost = Integer.MAX_VALUE;
				for (graph.NodeList i = nl; i != null; i = i.tail)
					if (ig.gtemp(i.head).getType() == 0 && !added.contains(i.head) && ig.spillCost(i.head) < minSpillCost)
					{
						minSpillCost = ig.spillCost(i.head);
						spillNode = i.head;
					}
				if (spillNode != null) {
					ns.push(spillNode);
					added.add(spillNode);
					for (graph.NodeList i = spillNode.pred(); i != null; i = i.tail)
						if (!added.contains(i.head))
							ig.rmEdge(i.head, spillNode);
				}
			}
		} while (spillNode != null);
		
//		for (graph.NodeList i = nl; i != null; i = i.tail)
//			if (ig.gtemp(i.head).getType() == 0 && !added.contains(i.head))
//				System.out.println("WRONG " + ig.gtemp(i.head));
		while (!ns.isEmpty()) {
			java.util.HashSet<temp.Temp> used = new java.util.HashSet<temp.Temp>();
			graph.Node top = ns.pop();
//			System.out.println(ig.gtemp(top));
			for (graph.NodeList i = top.succ(); i != null; i = i.tail)
				used.add(getColoredTemp(ig.gtemp(i.head)));
			for (temp.TempList i = registers; i != null; i = i.tail)
				if (!used.contains(i.head)) {
					map.put(ig.gtemp(top), i.head);
					break;
				}
		}
	}

}
